package main

import (
	"fmt"
)

type TreeNode struct {
	Val int
	Left *TreeNode
	Right *TreeNode
}
func dfs(root *TreeNode, distance int)([]int,int){
	depth:=make([]int,distance+1)
	if root.Left==nil && root.Right==nil{
		depth[0]=1
		return depth,0
	}
    var leftdepth,rightdepth=make([]int,distance+1),make([]int,distance+1)
	leftcount,righcount:=0,0
    if root.Left!=nil{
		leftdepth,leftcount=dfs(root.Left,distance)
	}
	if root.Right!=nil{
		rightdepth,righcount=dfs(root.Right,distance)
	}

	//算出左右子节点的深度节点数目，然后计算本层的深度
	for i:=0;i<distance;i++{
		depth[i+1]+=(leftdepth[i]+rightdepth[i])
	}
	//计算可能的好的节点对数
	cnt:=0
	for i:=0;i<=distance;i++{
		for j:=0;i+j+2<=distance;j++{
			cnt+=(leftdepth[i]*rightdepth[j])
		}
	}
	return depth,cnt+leftcount+righcount
}


func countPairs(root *TreeNode, distance int) int {
	if root==nil{
		return 0
	}
	_,cnt:=dfs(root,distance)
    return cnt
}

func main(){
	fmt.Println("hello")
}